// 解题思路：
// 遍历数组，使用当前元素和前面的元素作比较，看看能接到哪个元素后面
// 以该元素为结尾的最长递增子序列的长度 + 1，就是当前元素为结尾的最长递增子序列的长度
// 遍历一遍数组，时间复杂度为 O(N)
// 找前面元素的时候，也是需要遍历的，时间复杂度也是 O(N)，但是这个过程是可以通过贪心策略进行优化的
// 定义一个状态表示 dp[i] 表示长度为 i 的递增子序列结尾的最小元素
// 如果 nums[i] > dp[pos], 说明 nums[i] 可以接在 dp[pos] 后面，长度为 pos + 1
// 因此可以新开一个位置，让 dp[++pos] = nums[i]，如果是第一个元素，也需要新开位置
// 如果 nums[i] <= dp[pos]，可以通过二分的策略查找 nums[i] 可以放在 dp 中的哪个位置
// 假设可以放在 j 的位置，如果 nums[i] >= dp[j]，那就不需要变化，因为能接在 nums[i] 后面的，一定也可以接在 dp[j] 后面
// 如果 nums[i] < dp[j]，那么可以将 dp[j] = nums[i]，因为能接在 dp[j] 后面的，一定也能接在 nums[i] 后面

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int pos = 0;

        for(int i = 0; i < n; i++){
            if(pos == 0 || nums[i] > dp[pos]){
                dp[++pos] = nums[i];
            }else{
                int left = 1; int right = pos; int mid = 0;
                while(left < right){
                    mid = (right - left) / 2 + left;
                    if(dp[mid] < nums[i]){
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                if(nums[i] < dp[left]){
                    dp[left] = nums[i];
                }
            }
        }
        return pos;
    }
}
